\documentclass{article}
\usepackage[english]{babel}
\usepackage[letterpaper,top=2cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry}
\usepackage{xeCJK}
\usepackage{indentfirst}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{listings}
\usepackage{float}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{xcolor}
\usepackage{subfigure}%并排子图 共享标题 有子标题
\usepackage{array}
\usepackage{amsmath}
\usepackage{graphicx}
\graphicspath{image/}
\title{graph算法模板设计}
\author{舒开宸 3210103247}
\begin{document}
\maketitle
\section{设计思路框架}
\begin{figure}[hp]
  \centering
  \subfigure{
    \label{fig:subfig:onefunction} 
    \includegraphics[width=6cm]{image/1.png}}
  \hspace{0.5in} % 两图片之间的距离
  \subfigure{
    \label{fig:subfig:twofunction} 
    \includegraphics[width=6cm]{image/2.png}}
  \caption{顶点和边结构设计框架}
  \label{fig:twopicture} 
\end{figure}
\begin{figure}[hp]
  \centering
  \subfigure{
    \label{fig:subfig:onefunction} 
    \includegraphics[width=6cm]{image/3.png}}
  \hspace{0.5in} % 两图片之间的距离
  \subfigure{
    \label{fig:subfig:twofunction} 
    \includegraphics[width=6cm]{image/4.png}}
  \caption{父类模板函数全部被子类继承，子类有不同的数据存储模式}
  \label{fig:twopicture} 
\end{figure}
graph的实现方式有两种，分别是邻接表(GraphList)和邻接矩阵(GraphMatrix)两种，二者的本质区别就是边的存储模式是不同的，而所有的静态和动态操作函数都是一致的，故可以在父类Graph中定义一些列纯虚函数，如Figure 2的左图，两个子类，我的设计是adjacent matrix用的是嵌套向量存储，adjacent list用的是向量嵌套列表的方式存储。我遇到的问题是顶点的标号问题，如果不特殊处理的话顶点的标记只能按0,1,2,...增长，解决方式是输入建立一个vector类的tag,把标号推进vector里，这样就可以实现和自然数集的对应，把标号转化成相应的位置。由于代码写得很长，就不把代码呈现在报告中了，测试部分会提到设计思路。
\clearpage
\section{运行测试}
\subsection{邻接矩阵的运行测试}
\begin{figure}[hp]
    \centering
    \includegraphics[width=12cm]{image/5.png}
    \caption{输入值为3，8，6，9，12，14}
    \label{fig:my_label}
\end{figure}
\begin{figure}[hp]
    \centering
    \includegraphics[width=8cm]{image/6.png}
    \caption{输入一系列边，第一个数字用来跳出循环}
    \label{fig:my_label}
\end{figure}
\begin{figure}[hp]
    \centering
    \includegraphics[width=8cm]{image/7.jpg}
    \caption{图}
    \label{fig:my_label}
\end{figure}
我的测试文件test.cpp决定用那种储存方式根据用户输入来决定。根据提示，如果输入零则用邻接矩阵，输入其他则用邻接表。然后按提示输入以整数为标号的顶点，如果输入-1会跳出顶点输入，然后开始输入边，根据n,vertex i,vertex j,weight的方式输入四个整数，n没有传值作用，如果n为-1会跳出边输入的循环。
\clearpage
\begin{figure}[hp]
    \centering
    \includegraphics[width=8cm]{image/8.png}
    \caption{邻接矩阵的测试结果}
    \label{fig:my_label}
\end{figure}
\subsection{邻接表的运行测试}
\begin{figure}[hp]
    \centering
    \includegraphics[width=12cm]{image/9.png}
    \caption{输入数据为3，6，8，9，10，12，14}
    \label{fig:my_label}
\end{figure}
\begin{figure}[hp]
    \centering
    \includegraphics[width=8cm]{image/10.png}
    \caption{输入一系列边}
    \label{fig:my_label}
\end{figure}
\begin{figure}[hp]
    \centering
    \includegraphics[width=8cm]{image/11.jpg}
    \caption{图}
    \label{fig:my_label}
\end{figure}
\begin{figure}[hp]
    \centering
    \includegraphics[width=6cm]{image/12.png}
    \caption{邻接表的运行结果}
    \label{fig:my_label}
\end{figure}
\end{document}